package practice_2025_7_15;

import java.util.Arrays;
import java.util.Stack;

public class Solution {
    /**
     * 最长公共前缀
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        StringBuffer res = new StringBuffer();
        for(int i = 0; i < strs[0].length(); i++) {
            char ch = strs[0].charAt(i);
            for(int j = 1; j < strs.length; j++) {
                try {
                    if (strs[j].charAt(i) != ch) {
                        //   System.out.println(strs[j].length() + " " + strs[j].charAt(i) + " " + i);
                        //    System.out.println("res1: " + (strs[j].length() <= i + 1) + " res2: " + (strs[j].charAt(i) != ch));
                        return res.toString();
                    }
                } catch(IndexOutOfBoundsException e) {
                    return res.toString();
                }
            }
            res.append(ch);
        }
        return res.toString();
    }

    /**
     * 二进制求和
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b) {
        // 从低位向高位计算
        int indexA = a.length() - 1;
        int indexB = b.length() - 1;
        StringBuffer res = new StringBuffer();

        int sum = 0, carry = 0;
        while(indexA >= 0 && indexB >= 0) {
            // 1 1 -> 2 -> 0 1
            int tmp = (a.charAt(indexA) - '0') + (b.charAt(indexB) - '0') + carry;
            carry = tmp / 2;
            sum = tmp % 2;
            res.append(sum);
            indexA--;
            indexB--;
        }
        while (indexA >= 0) {
            int tmp = (a.charAt(indexA) - '0') + carry;
            carry = tmp / 2;
            sum = tmp % 2;
            res.append(sum);
            indexA--;
        }
        while (indexB >= 0) {
            int tmp = (b.charAt(indexB) - '0') + carry;
            carry = tmp / 2;
            sum = tmp % 2;
            res.append(sum);
            indexB--;
        }
        while(carry > 0) {
            sum = carry % 2;
            carry = carry / 2;
            res.append(sum);
        }
        return res.reverse().toString();
    }

    /**
     * 字符串相乘
     * @param num1
     * @param num2
     * @return
     */
    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int[] sum = new int[len1 + len2];
        for(int i = len1 - 1; i >= 0; i--) {
            for(int j = len2 - 1; j >= 0; j--) {
                int index = (len1 - 1 - i + len2 - 1 - j);
                sum[index] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            }
        }
        // System.out.println(Arrays.toString(sum));
        // 计算
        int carry = 0;
        int count = 0;
        StringBuffer res = new StringBuffer();
        for(int i = 0; i < sum.length; i++) {
            count = (sum[i] + carry) % 10;
            carry = (sum[i] + carry) / 10;
            res.append(count);
        }
        res = res.reverse();
        while(res.length() > 0 && res.charAt(0) == '0') {
            res.deleteCharAt(0);
        }
        return (res.length() <= 0) ? "0" : res.toString();
    }

    /**
     * 基本计算器
     * @param s
     * @return
     */
    public int calculate(String s) {
        char op = '+';
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        while(i < s.length()) {
            char ch = s.charAt(i);
            i++;
            if (ch >= '0' && ch <= '9') {
                int n = ch - '0';
                while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    n = n * 10 + (s.charAt(i) - '0');
                    i++;
                }
                //        System.out.println("ch: " + n + " op: " + op);
                switch(op) {
                    case '+':
                        stack.push(n);
                        break;
                    case '-':
                        stack.push( -n);
                        break;
                    case '*':
                        int num1 = 1;
                        if (stack.size() >= 1) {
                            num1 = stack.pop();
                        }
                        stack.push(num1 * n);
                        break;
                    case '/':
                        int num = 1;
                        if (stack.size() >= 1) {
                            num = stack.pop();
                        }
                        // System.out.println(num);
                        stack.push(num / n);
                        break;
                }
            } else if (ch == ' ') {
            } else {
                op = ch;
            }
        }
        int res = 0;
        while(!stack.isEmpty()) {
            res += stack.pop();
        }
        return res;
    }

    /**
     * 验证栈序列
     * @param pushed
     * @param popped
     * @return
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while(!stack.isEmpty() && j < popped.length && popped[j] == stack.peek()) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}
